Bloom Filter
Operations
集合を管理する．$ k 個のハッシュ関数が必要で，これらはハッシュとして$ [0,m) の整数を返すものとする．
空間計算量$ \Theta(m)
$ \mathtt{new}()
空の Bloom filter を作成する
時間計算量$ \Theta(m)
$ \mathtt{insert}(x)
集合に$ xを追加する
時間計算量$ \Theta(k)
$ \mathtt{probably\_contains}(x)
集合が$ xを含む可能性があるか判定する
時間計算量$ \Theta(k)
Summary
長さ$ mのビット配列．すべて$ 0で初期化する．
要素を追加する際は，$ [0, m)のハッシュ値を$ k個計算し，それらの添字のビットをすべて$ 1にする．
要素が含まれるか調べたいときは，同じようにハッシュ値を$ k個計算し，それらの添字のビットがすべて$ 1なら含まれる可能性がある．そうでない場合は確実に含まれない．
確率的データ構造の一つ．
要素が含まれる場合は常に検出できるが，含まれない場合にも含まれると報告することがある (偽陽性)．
$ k=3,m=10の例：
https://gyazo.com/1755ffc11320cdc9c8c9a6906de4cab2
References
Notes
偽陽性の発生率と空間はトレードオフの関係にあり，$ k, mを適切に選ぶことで調整できる．
要素の削除はできない．ビット配列の代わりに整数値の配列を用意しカウンタとして用いるという自然な拡張で削除が可能となる (ただし依然として偽陽性は残る；含まれない要素を削除できてしまうことがある) → Counting Filter